package com.example.algorithm.huawei_rongyao_29;

import java.util.*;

// 不重复打印排序数组中相加和为给定值的所有三元组
/**
 * 标题：不重复打印排序数组中相加和为给定值的所有三元组 | 时间限制：2秒 | 内存限制：262144K
 * 给定排序数组arr和整数k，不重复打印arr中所有相加和为k的严格升序的三元组
 * 例如, arr = [-8, -4, -3, 0, 1, 1, 2, 4, 5, 8, 9],
 *
 * 输入：
 * 11 10
 * -8 -4 -3 0 1 1 2 4 5 8 9
 * 打印结果为：
 * -4 5 9
 * -3 4 9
 * -3 5 8
 * 0 1 9
 * 0 2 8
 * 1 4 5
 * 其中三元组1 1 8不满足严格升序所以不打印
 *
 * [要求]
 * 时间复杂度为0(n2),空间复杂度为o(1)
 *
 * 输入描述:
 * 第一行有两个整数n, k
 * 接下来一行有n个整数表示数组内的元素
 *
 * 输出描述:
 * 输出若干行，每行三个整数表示答案
 * 按三元组从小到大的顺序输出(三元组大小比较方式为每个依次比较三元组内每个数)
 *
 * 备注:
 * 示例1
 * 输入
 * 10 10
 * -8 -4 -3 0 1 2 4 5 8 9
 * 输出
 * -4 5 9
 * -3 4 9
 * -3 5 8
 * 0 1 9
 * 0 2 8
 * 1 4 5
 *
 * 示例2
 * 输入
 * 11 10
 * -8 -4 -3 0 1 1 2 4 5 8 9
 * 输出
 * -4 5 9
 * -3 4 9
 * -3 5 8
 * 0 1 9
 * 0 2 8
 * 1 4 5
 *
 * 示例3
 * 输入
 * 11 10
 * -8 -4 -3 0 1 1 2 4 4 8 9
 * 输出
 * -3 4 9
 * 0 1 9
 * 0 2 8
 *
 * 思路
 * 我们可以利用双指针法来实现这一目标。具体步骤如下：
 * <p>
 * 遍历数组：固定第一个元素。
 * 双指针法：对于每个固定的第一个元素，使用双指针在剩下的部分寻找另外两个元素，使得这三个元素的和为 k。
 * 去重：为了避免重复的三元组，确保在选择第一个元素和双指针元素时跳过相同的元素。
 * 步骤
 * 读取输入：读取数组长度 n 和目标和 k，以及数组元素。
 * 遍历数组：固定第一个元素。
 * 双指针搜索：使用两个指针从固定元素后的部分开始，一个从左边，一个从右边，寻找符合条件的元素。
 * 去重处理：确保结果中没有重复的三元组。
 * <p>
 * <p>
 *
 * 代码解释
 * 读取输入：
 * <p>
 * 使用 Scanner 读取输入的数组长度 n 和目标和 k，然后读取数组元素存入 arr 中。
 * 排序数组：
 * <p>
 * 使用 Arrays.sort(arr) 对数组进行排序。
 * 寻找三元组：
 * <p>
 * 遍历数组，固定第一个元素。
 * 对于每个固定的第一个元素，使用双指针法寻找另外两个元素。
 * 当找到一个符合条件的三元组时，加入结果列表，并移动指针跳过相同的元素以避免重复。
 * 输出结果：
 * <p>
 * 遍历结果列表，按要求的格式输出每个三元组。
 *
 *
 * 以下程序经过实际运行测试，是OK的。
 */

public class Q19_ThreeSum {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        String line1 = scanner.nextLine();
        int[] arr1 = Utils.scannerAndTransIntoInt(line1);
        int n = arr1[0];
        int k = arr1[1];

        String line2 = scanner.nextLine();
        int[] arr2 = Utils.scannerAndTransIntoInt(line2);

        List<List<Integer>> result = findThreeSum(arr2, k);

        for (List<Integer> triplet : result) {
            System.out.println(triplet.get(0) + " " + triplet.get(1) + " " + triplet.get(2));
        }
    }

    public static List<List<Integer>> findThreeSum(int[] arr, int k) {
        List<List<Integer>> results = new ArrayList<>();
        Arrays.sort(arr);

        for (int i = 0; i < arr.length - 2; i++) {

            // Skip duplicate elements to avoid duplicate triplets
            // for example, arr[i] =1,arr[i - 1]=1,so we skip current loop
            // This is only for the pointer `i`, allowing it to skip over duplicate elements as it moves.
            if (i > 0 && arr[i] == arr[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = arr.length - 1;

            while (left < right) {
                int sum = arr[i] + arr[left] + arr[right];

                if (sum == k) {
                    results.add(Arrays.asList(arr[i], arr[left], arr[right]));

                    // Move pointers and skip duplicates
                    // 这个跳过重复元素和上面那个i指针的跳过重复元素不冲突，人家这个是针对left和right的
                    while (left < right && arr[left] == arr[left + 1]) {
                        left++;
                    }
                    while (left < right && arr[right] == arr[right - 1]) {
                        right--;
                    }

                    //为什么命中一次k值之后，要同时left++和right--呢。
                    // 想象一下，整体上下文i不变的情况下，sum = arr[i] + arr[left] + arr[right];我们的目标是下一轮while (left < right)进来继续寻找sum等于k的。
                    // 仅仅右移left，sum一定大于k。仅仅左移right，sum一定小于k。相当于j与k任何一个都绝对不能留，并且同时向内移动是唯一的选择。所以要想程序达到目的必须要移动。
                    left++;
                    right--;
                } else if (sum < k) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return results;
    }
}






